package com.zhz.leetcode;

import com.zhz.leetcode.entity.ListNode;
import com.zhz.leetcode.utils.LinkedListUtils;

/**
 * 206.反转链表
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class ReverseLinkedList206 {

    public static void main(String[] args) {
        ReverseLinkedList206 m = new ReverseLinkedList206();
        ListNode node1 = m.createNode();
        ListNode head = m.reverseList3(node1);
        LinkedListUtils.printList(head);
    }

    /**
     * 学习创建链表
     */
    public ListNode createNode() {
        ListNode head1 = new ListNode(-1);
        ListNode curr = head1;
        for (int i = 1; i <= 7; i++) {
            curr.next = new ListNode(i);
            curr = curr.next;
        }
        LinkedListUtils.printList(head1.next);
        return head1.next;
    }

    /**
     * 个人实现的写法
     * 迭代
     * 思路: 只取node1的值，然后将next插入到表头，最终形成反转
     * 链表保持链接状态  第一次迭代之后 （2,1,3,4,5,6,7）
     * 第二次： (3,2,1,4,5,6,7)
     * ...
     * 最总实现反转
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode newHead = head;
        ListNode next;
        while (head.next != null) {
            next = head.next;
            head.next = next.next;
            next.next = newHead;
            newHead = next;
        }
        return newHead;
    }


    /**
     * 官方解法
     * 迭代
     * 思路: 取出当前curr的next值，插入到表头，并将curr置为原先的next位置，然后继续重复的步骤
     * 每次迭代都将头节点取出来，然后将next插入到新的链表头结点上
     * 比如说第一次迭代之后 就有两个链表  分别是(1)和(2,3,4,5,6,7)
     * 第二次迭代 ：(2,1)和(3,4,5,6,7)
     * ...
     * 最终实现链表反转
     */
    public ListNode reverseList1(ListNode head) {
        ListNode newHead = null;
        ListNode curr = head;
        ListNode next;
        while (curr != null) {
            next = curr.next;
            curr.next = newHead;
            newHead = curr;
            curr = next;
        }
        return newHead;
    }

    /**
     * 考虑到题目没有禁止重新创建节点，因此可以利用重新创建节点的写法，每次迭代都重新创建新的头节点，然后next指向上一次创建的头节点上
     */
    public ListNode reverseList2(ListNode head) {
        ListNode tmp = null;
        ListNode curr = head;
        while (curr != null) {
            tmp = new ListNode(curr.val, tmp);
            curr = curr.next;
        }
        return tmp;
    }


    /**
     * 与reverseList2的解法思路一样，只不过换成for循环进行迭代
     */
    public ListNode reverseList3(ListNode head) {
        ListNode tmp = null;
        for (ListNode i = head; i != null; i = i.next) {
            tmp = new ListNode(i.val, tmp);
        }
        return tmp;
    }

}
